package com.algrithom.array;

/**
 * 1918. 第 K 小的子数组和·
 */
public class Solution9 {
    
    public static void main(String[] args){
        int[] nums = new int[]{3,3,5,5};
        Solution9 solution9 = new Solution9();
        System.out.println(solution9.kthSmallestSubarraySum(nums,7));
    }
    
    public int kthSmallestSubarraySum(int[] nums,int k){
        int len = nums.length;
        int minValue = Integer.MAX_VALUE;
        int sum = 0;
        for (int i = 1; i <= len; i++) {
            minValue = Math.min(minValue,nums[i - 1]);
            sum += nums[i - 1];
        }
        int left = minValue;
        int right = sum;
        while (left <= right) {
            int mid = (right - left) / 2 + left;
            int total = count(nums,mid);
            if (total < k) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
    
    private int count(int[] nums,int mid){
        int len = nums.length;
        int sum = 0;
        int total = 0;
        int left = 0;
        int right = 0;
        while (right < len) {
            sum += nums[right];
            while (sum > mid) {
                sum -= nums[left];
                left++;
            }
            total += right - left + 1;
            right++;
        }
        return total;
    }
}
